|
In cryptography, a major goal is to create cryptographic primitives with provable security. In some cases, cryptographic protocols are found to have information theoretic security; the one-time pad is a common example. However, information theoretic security cannot always be achieved; in such cases, cryptographers fall back to computational security. Roughly speaking, this means that these systems are secure ''assuming that any adversaries are computationally limited'', as all adversaries are in practice. Because ''hardness'' of a problem is difficult to prove, in practice certain problems are "assumed" to be difficult. ==Common cryptographic hardness assumptions== There are many common cryptographic hardness assumptions. While the difficulty of solving any of the underlying problems is unproven, some assumptions on the computational hardness are stronger than others. Note that if assumption A is ''stronger'' than assumption B, that means solving the problem underlying assumption B ''is polytime reducible to'' solving the problem underlying assumption A – which means that if B is solvable in poly time, A definitely is, but the reverse doesn't follow. When devising cryptographic protocols, one hopes to be able to prove security using the ''weakest'' possible assumptions. This is a list of some of the most common cryptographic hardness assumptions, and some cryptographic protocols that use them. *Integer factorization * *Rabin cryptosystem * *Blum Blum Shub generator * *Okamoto–Uchiyama cryptosystem * *Hofheinz–Kiltz–Shoup cryptosystem *RSA problem (weaker than factorization) * *RSA cryptosystem *Quadratic residuosity problem (stronger than factorization) * *Goldwasser–Micali cryptosystem *Decisional composite residuosity assumption (stronger than factorization) * *Paillier cryptosystem *Higher residuosity problem (stronger than factorization) * *Benaloh cryptosystem * *Naccache–Stern cryptosystem *Phi-hiding assumption (stronger than factorization) * *Cachin–Micali–Stadler PIR *Discrete log problem (DLP) *Computational Diffie–Hellman assumption (CDH; stronger than DLP) * *Diffie–Hellman key exchange *Decisional Diffie–Hellman assumption (DDH; stronger than CDH) * *ElGamal encryption *Shortest Vector Problem * *NTRUEncrypt * *NTRUSign 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「computational hardness assumption」の詳細全文を読む スポンサード リンク
|